/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import java.util.HashMap;


/**
 * @version 1.0
 * @description Design and implement a data structure for Least Recently Used
 *              (LRU) cache. It should support the following operations: get and
 *              set.
 * 
 *              get(key) - Get the value (will always be positive) of the key if
 *              the key exists in the cache, otherwise return -1. set(key,
 *              value) - Set or insert the value if the key is not already
 *              present. When the cache reached its capacity, it should
 *              invalidate the least recently used item before inserting a new
 *              item.
 */
public class LRUCache {
	
	private class Element {
		int key;
		int value;
		Element pre;
		Element next;
		
		public Element(int key, int value) {
			this.key = key;
			this.value = value;
			pre = null;
			next = null;
		}
	}
	
	private int capacity;
	private HashMap<Integer, Element> map; 
	private Element head;
	private Element tail;
	
	public LRUCache(int capacity) { 
		this.capacity = capacity;
		map = new HashMap<>();
		head = new Element(0, 0);
		tail = new Element(0, 0);
		head.next = tail;
		tail.pre = head;
	}

	public int get(int key) {
		if (!map.containsKey(key))
			return -1;
		Element cur = map.get(key);
		cur.pre.next = cur.next;
		cur.next.pre = cur.pre;
		attach(cur);
		return cur.value;
	}

	public void set(int key, int value) {
		if (map.containsKey(key)) {
			Element cur = map.get(key);
			cur.pre.next = cur.next;
			cur.next.pre = cur.pre;
			cur.value = value;
			attach(cur);
		} else {
			if (map.size() == capacity)
				dettach();
			Element cur = new Element(key, value);
			attach(cur);
			map.put(key, cur);
		}
	}
	
	private void attach(Element element) {
		element.pre = tail.pre;
		tail.pre.next = element;
		element.next = tail;
		tail.pre = element;
	}
	
	public void dettach() {  
		Element e = head.next;
		head.next = head.next.next;
		head.next.pre = head;
		map.remove(e.key);
    }  
	
}
